#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
	pair<int, int> count_eval(string &s, int l, int r)
	{
		if (l == r) {
			return s[l] == '0' ? pair<int, int>(0, 1) : pair<int, int>(1, 0);
		}

		pair<int, int> ans;
		for (int i = l + 1; i < r; i += 2) {
			auto left = count_eval(s, l, i - 1);
			auto right = count_eval(s, i + 1, r);
			if (s[i] == '&') {
				ans.first += left.first * right.first;
				ans.second += left.first * right.second + left.second * right.first + left.second * right.second;
			}
			if (s[i] == '|') {
				ans.first += (left.first + left.second) * (right.first + right.second) - left.second * right.second;
				ans.second += left.second * right.second;
			}
			if (s[i] == '^') {
				ans.first += left.first * right.second + left.second * right.first;
				ans.second += left.first * right.first + left.second * right.second;
			}
		}
		return ans;
	}

	int count_eval(string s, int result)
	{
		int n = s.size();
		vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n, pair<int, int>(0, 0)));

		for (int i = 0; i < n; i += 2) {
			dp[i][i] = s[i] == '1' ? pair<int, int>(1, 0) : pair<int, int>(0, 1);
		}

		for (int col = 2; col < n; col += 2) {
			for (int l = 0, r = col; r < n; l += 2, r += 2) {
                                pair<int, int> ans;
				for (int i = l + 1; i < r; i += 2) {
					auto left = dp[l][i - 1];
					auto right = dp[i + 1][r];
					if (s[i] == '&') {
						ans.first += left.first * right.first;
						ans.second += left.first * right.second + left.second * right.first + left.second * right.second;
					}
					if (s[i] == '|') {
						ans.first += (left.first + left.second) * (right.first + right.second) - left.second * right.second;
						ans.second += left.second * right.second;
					}
					if (s[i] == '^') {
						ans.first += left.first * right.second + left.second * right.first;
						ans.second += left.first * right.first + left.second * right.second;
					}
				}
                                dp[l][r] = ans;
			}
		}
                return result == 1 ? dp[0][n - 1].first : dp[0][n - 1].second;
	}

    public:
	int countEval(string s, int result)
	{
		// auto ans = count_eval(s, 0, s.size() - 1);
		// return result == 1 ? ans.first : ans.second;
                return count_eval(s, result);
	}
};

int main()
{
	string s = "0&0&0&1^1|0";
	int result = 1;
	cout << Solution().countEval(s, result) << endl;
	return 0;
}